package consistenthash

import (
	"hash/crc32"
	"sort"
	"strconv"
)

//Hash maps bytes to uint32
type Hash func(data []byte)uint32
//默认为 crc32.ChecksumIEEE 算法

//Map constains all hashed key
type Map struct{
	hash Hash//hash函数
	replicas int//虚拟节点倍数
	keys []int//哈希环
	hashMap map[int]string//虚拟节点与真实节点的映射表
	//键是虚拟节点的哈希值，值是真实节点的名称。
}

//New creates a Map instance
//允许自定义虚拟节点倍数和 Hash 函数。
func New(replicas int,fn Hash)*Map{
	m := &Map{
		replicas:replicas,
		hash: fn,
		hashMap: make(map[int]string), 
	}
	if m.hash == nil{
		m.hash = crc32.ChecksumIEEE
	}
	return m
}

//Add adds some keys to the hash
func (m *Map)Add(keys ...string){
	for _,key := range keys{
		for i := 0;i < m.replicas;i++{
			hash := int(m.hash([]byte(strconv.Itoa(i)+key)))
			//虚拟节点的名称是：strconv.Itoa(i) + key，
			//即通过添加编号的方式区分不同虚拟节点。
			m.keys = append(m.keys,hash)
			m.hashMap[hash] = key//增加虚拟节点和真实节点的映射关系
		}
	}
	sort.Ints(m.keys)
	//环上的哈希值排序
}

//Get gets the closest item in the hash to the provided key
func (m *Map)Get(key string)string{
	if len(m.keys)==0{
		return ""
	}
	hash := int(m.hash([]byte(key)))
	//Binary search for appropriate replica
	idx := sort.Search(len(m.keys),func(i int)bool{
		return m.keys[i] >= hash
	})
	return m.hashMap[m.keys[idx%len(m.keys)]]
	//找不到就是idx=len(m.keys),就映射到第一个hash值
}

